//给定一个 没有重复 数字的序列，返回其所有可能的全排列。 
//
// 示例: 
//
// 输入: [1,2,3]
//输出:
//[
//  [1,2,3],
//  [1,3,2],
//  [2,1,3],
//  [2,3,1],
//  [3,1,2],
//  [3,2,1]
//] 
// Related Topics 回溯算法 
// 👍 853 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

//Java：全排列
public class P46Permutations {

    /**
     *
     * 思路： 回溯算法， 按顺序取数字，如果取满 nums.length 个回溯
     *
     * 执行用时： 4 ms , 在所有 Java 提交中击败了 25.15% 的用户 内存消耗： 40 MB , 在所有 Java 提交中击败了 56.03% 的用户
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private List<List<Integer>> list = new ArrayList<>();

        public List<List<Integer>> permute(int[] nums) {
            if (nums.length != 0) {
                dfs(nums, new Stack<>());
            }
            return list;
        }

        private void dfs(int[] nums, Stack<Integer> path) {
            if (path.size() == nums.length) {
                list.add(new ArrayList<>(path));
                return;
            }

            for (int start = 0; start < nums.length; start++) {
                // 如果多建一个数组来存是否使用过，而不是用 contains 方法，速度可能会快一点
                if (path.contains(nums[start])) {
                    continue;
                }
                path.push(nums[start]);
                dfs(nums, path);
                path.pop();
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P46Permutations().new Solution();
        int[] nums = new int[]{};
        solution.permute(nums);
        // TO TEST
    }

}